#ifndef COIN_H
#define COIN_H

#include <algorithm>
using namespace std;

/**
 * @brief 在限制各币值硬币数目的情况下，求达到目标金额的最小硬币数
 * 
 * @param coins 
 * @param MAX 
 * @param n 
 * @param money 
 * @return int 
 */
int coin_change(vector<int>& coins, vector<int>& MAX, int n, int money){
    vector<vector<int>> dp(n + 1, vector<int>(money + 1, INT_MAX));   // dp[i][j]表示使用前i种硬币凑成金额j所需的最小硬币数
    dp[0][0] = 0;                                                     // 金额为0时，所需硬币数为0
    for(int i = 1; i <= n; i++){                                      // 从第1种硬币开始往后递推
        for (int j = 0; j <= money; j++){    
            dp[i][j] = dp[i - 1][j];                                  // 不使用当前硬币
            int MaxCount = min(MAX[i-1], j / coins[i-1]);             // 当前硬币最大可用数量
            for (int k = 1;k <= MaxCount;k++){
                if(j >= k * coins[i - 1] && dp[i-1][j - k * coins[i-1]]!= INT_MAX){
                    dp[i][j] = min(dp[i][j],dp[i-1][j-k*coins[i-1]]+k);
                }
            }            
        }
    }
    return dp[n][money] == INT_MAX ? -1 : dp[n][money];               // 如果无解则返回-1
}

#endif